import java.util.LinkedList;
import java.util.Queue;
class BTNode<T> {
    T data;
    BTNode left;
    BTNode right;

    public BTNode() {
        left = right = null;
    }
    public BTNode(T e) {
        data = e;
        left = right = null;
    }
}
public class BTree<T> {
    BTNode<T> root;
    String res;

    public BTree() {
        root = null;
    }

    public String BracketOut(){
        res = "";
        _BracketOut(root);
        return res;
    }

    public void _BracketOut(BTNode<T> root) {
        if(root!=null){
            res+=root.data;
            if(root.left!=null||root.right!=null){
                res+="(";
                _BracketOut(root.left);
                if(root.right!=null)
                    res+=",";
                _BracketOut(root.right);
                res+=")";
            }
        }
    }

    public void PreOrder(){
        _PreOrder(root);
        System.out.println();
    }

    public void _PreOrder(BTNode<T> root) {
        if(root!=null){
            System.out.print(root.data+" ");
            _PreOrder(root.left);
            _PreOrder(root.right);
        }
    }

    public void InOrder(){
        _InOrder(root);
        System.out.println();
    }
    public void _InOrder(BTNode<T> root) {
        if(root!=null){
            _InOrder(root.left);
            System.out.print(root.data+" ");
            _InOrder(root.right);
        }
    }

    public void PostOrder(){
        _PostOrder(root);
        System.out.println();
    }
    public void _PostOrder(BTNode<T> root) {
        if(root!=null){
            _PostOrder(root.left);
            _PostOrder(root.right);
            System.out.print(root.data+" ");
        }
    }

    public void LevelOrder() {
        if(root==null)
            return ;

        Queue<BTNode<T>> q= new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            BTNode<T> t = q.remove();
            if(t.left!=null)
                q.add(t.left);
            if(t.right!=null)
                q.add(t.right);
            System.out.print(t.data+" ");
        }
        System.out.println();
    }

}
